package com.mlh.greed;

/**
 * @author 缪林辉
 * @date 2024/4/10 10:27
 * @DESCRIPTION
 */
// 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
// 在每一天，你可以决定是否购买和/或出售股票。
// 你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
// 返回 你能获得的 最大 利润 。
public class 买卖股票的最佳时机2 {
    // 贪心策略：
    // 买入 ：观察 i 和i+1 如果 i<i+1 购入股票
    // 卖出 ：观察i+2是否>i+1 如果是  则不断循环 直到后一个元素小于前一个元素  卖出股票
    public int method1(int[] prices) {
        int buy = 0;
        int sell = 1;
        int profit = 0;
        while (buy < prices.length - 1 && sell < prices.length) {
            if (prices[buy] < prices[sell]) {// i<i+1 购入股票
                profit -= prices[buy];
                // 观察i+2是否>i+1 如果是  则不断循环 直到后一个元素小于前一个元素  卖出股票
                while (sell < prices.length - 1 && prices[sell] < prices[sell + 1]) {
                    sell += 1;
                }
                profit += prices[sell];
                // 开始新的一轮买入和卖出
                buy = sell;
                sell = buy + 1;
            }
            buy++;
            sell++;
        }
        return profit;
    }

    // 代码随心录中的解法
    // 他的解法思路更巧妙
    // 假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。
    // 相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
    // 此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！
    // 计算出每天的利润，收集每天的正利润，就可以达到全局最优
    public int method2(int[] prices) {
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }

}
